package com.sicheng.lc.周赛.分类.dp;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/10 11:20
 */
public class 统计理想数组的数目 {
    //https://leetcode.cn/problems/count-the-number-of-ideal-arrays/
    static int mod = (int) (1e9 + 7);
    static int N = (int) 1e4;
    static ArrayList<Integer>[] p = new ArrayList[N + 1];
    // 预处理 j 的所有因子
    static {
        Arrays.setAll(p, k -> new ArrayList<>(150));
        for (int i = 1; i <= N; i++) {
            for (int j = i; j <= N; j += i) {
                p[j].add(i);
            }
        }
    }

    // 复杂度： n * maxValue * 100 约 1e9~1e10 超时
    // todo 优化复杂度
    public int idealArrays(int n, int maxValue) {
        // dp[i,j] 长度为i的子数组以j结尾并满足整除条件的个数
        int[] dp = new int[maxValue + 1];
        for (int i = 1; i <= maxValue; i++) {
            dp[i] = 1;
        }
        // 状态转移
        // dp[i,j] = sum(dp[i-1,k]) k是j的因子
        //>>>>>>>>>>>>>第一行是j的序号[1,2,3...]>>第一列是i的序号[1,2,3.....]>>>>>>
        // dp|   1    2     3     4     5
        //  1|   1    1     1     1     1
        //  2|   1    2     2     3     2
        //  3|   1    3     3     6     3
        //  4|   1    4     4     10    4
        //  据实际例子说明
        //  dp[2,5]= dp[1,5] + dp[1,1] = 2;          dp[2,5]表示长度为2的子数组以5结尾满足整除条件的个数,5的因子(1,5)
        //  dp[2,4]= dp[1,1] + dp[1,2] + dp[1,4] = 3;dp[2,4]表示长度为2的子数组以4结尾满足整除条件的个数,4的因子(1,2,4)
        //  实际上 dp 可以降低到一维
        for (int i = 2; i <= n; i++) {
            for (int j = maxValue; j >= 1; j--) {
                for (int x : p[j]) {
                    if (x == j)
                        break;
                    dp[j] = (dp[j] + dp[x]) % mod;
                }
            }
        }
        int sum = 0;
        for (int j : dp) {
            sum = (sum + j) % mod;
        }
        return sum;
    }

    public static void main(String[] args) {
        统计理想数组的数目 s = new 统计理想数组的数目();
        int x = s.idealArrays(100, 100);
        System.out.println(x);
    }

}
